package singleLinkedList;

public class Main {

    //合并两个有序结点(从小到大）
    public Node mergeTwoLists(Node head1,Node head2) {
        // 新建一个虚拟结点
        Node newHead = new Node(-1); // 要让该结点保持不变，稍后好进行返回
        Node tmp = newHead;
        // 开始依次进行大小比较
        while(head1!=null && head2!=null) {
            if(head1.val > head2.val) {
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            } else {
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }
        }
        // 出来则说明要么head1==null 要么head2==null （短路原则）
        if(head1==null) {
            tmp.next = head2;
        }
        if (head2==null) {
            tmp.next = head1;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        System.out.println("使用穷举法进行链表创建：");
        singleLinkedList.createList();

        System.out.println("进行完全打印：");
        singleLinkedList.display();

        System.out.println("头插法插入：");
        singleLinkedList.addFirst(1998);
        singleLinkedList.display();

        System.out.println("尾插法插入：");
        singleLinkedList.addLast(725);
        singleLinkedList.display();

        System.out.println("计算链表长度：");
        System.out.println(singleLinkedList.size());

        System.out.println("位置插入：");
        singleLinkedList.addIndex(2,1998);
        singleLinkedList.display();

        System.out.println("判断链表是否包含关键字key：");
        System.out.println(singleLinkedList.contains(8));

        System.out.println("删除首次关键字key：");
        singleLinkedList.remove(1998);
        singleLinkedList.display();

        System.out.println("删除所有出现的关键字key:");
        singleLinkedList.removeAllKey(1998);
        singleLinkedList.display();

        System.out.println("进行链表反转：");
        singleLinkedList.display(singleLinkedList.reverseList());

        System.out.println("进行链表寻找中间结点：");
        Node middleNode = singleLinkedList.middleNode();
        System.out.println("进行中间结点的打印：");
        singleLinkedList.printNode(middleNode);

        System.out.println("进行链表倒数第k个结点：");
        Node findKthToTail = singleLinkedList.findKthToTail(3);
        System.out.println("进行倒数第k个结点的打印：");
        singleLinkedList.printNode(findKthToTail);

        System.out.println("创建两个有序链表：");
        SingleLinkedList sll1 = new SingleLinkedList();
        sll1.addLast(2);
        sll1.addLast(8);
        sll1.addLast(98);
        System.out.print("打印链表1：");
        sll1.display();
        SingleLinkedList sll2 = new SingleLinkedList();
        sll2.addLast(3);
        sll2.addLast(22);
        sll2.addLast(19);
        sll2.addLast(28);
        sll2.addLast(3);
        System.out.print("打印链表2：");
        sll2.display();
        System.out.println("合并两个有序链表：");
        Main mmain = new Main();
        Node mergeTwo = mmain.mergeTwoLists(sll1.head,sll2.head);
        singleLinkedList.display(mergeTwo);

        System.out.println("以定值x进行分割：");
        Node part = singleLinkedList.partition(6);
        singleLinkedList.display(part);
        //singleLinkedList.display();  //此处其实是有一个问题：该链表的缺少了一个结点!!!

        //写为回文链表，目的是为了判断回文链表方法的正确性
        System.out.println("进行链表添加结点：");
        //singleLinkedList.addLast(8);
        singleLinkedList.addLast(725);
        singleLinkedList.addLast(2);
        singleLinkedList.display();

        System.out.println("判断是否为回文链表：");
        System.out.println(singleLinkedList.chkPalindrome());

        System.out.println("使得两个链表进行相交：");
        //singleLinkedList.createCur(sll1,sll2);// 注意参数形式！！
        singleLinkedList.createCur(sll1.head,sll2.head);
        sll1.display();
        sll2.display();
        System.out.println("寻找相交结点的值：");
        Node interNode = singleLinkedList.getIntersectionNode(sll1.head,sll2.head);
        singleLinkedList.printNode(interNode);

        System.out.println("进行mergeTwo逆序打印（递归）：");
        singleLinkedList.printReverse(mergeTwo);
        System.out.println();

        System.out.println("进行mergeTwo逆序打印（利用栈）：");
        singleLinkedList.printReverseStack(mergeTwo);

        System.out.println("设计有环链表：");
        singleLinkedList.cycle(sll1.head);
        //sll1.display(); // 一直不停输出 已经形成环
        System.out.println("判断是否为有环链表：");
        System.out.println(sll1.hasCycle());

        System.out.println("寻找有环链表的入口点：");
        Node detectNode = sll1.detectCycle();
        singleLinkedList.printNode(detectNode);

        System.out.println("进行链表清空：");
        singleLinkedList.clear();
        singleLinkedList.display();
    }
}
